package com.lbc.dataStruce;

public class Aii {
    //  求出满足 a[i] = i 时的下标  且  O(logn)
    public static void main(String[] args) {
        int [] arr = {1,2,3,4,4,6,7,8,8};
        int resIndex = binarySearch(arr, 0, arr.length - 1);
        System.out.println("resIndex = " + resIndex);
    }

    /**
     *    二分分治查找
     * @param arr    数组
     * @param left   左边的索引
     * @param right  右边的索引
     * @return  找到就返回下标，没找到就返回 -1
     */
    public static int binarySearch (int [] arr, int left, int right) {
        //  如果 left > right ，说明分治完整个数组了，但是没有找打
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;  // 中分点

        if (mid == arr[mid]) {
            return mid;    //  结果
        } else {
            // 向右分治
            int resIndex = binarySearch(arr, mid + 1, right);
            if (resIndex == -1) {  // 说明没找到
                // 向左分治
                resIndex = binarySearch(arr, left, mid - 1);
            }
            return resIndex;
        }
    }


}
